A link state routing protocol is a routing protocol used in packet switching networks. Examples of link state routing protocols include open shortest path first (OSPF) and intermediate system to intermediate system (IS-IS). For link state routing, the nodes construct a map of the connectivity to the network, e.g., in the form of a graph, showing which nodes are connected to which other nodes. Each node may then independently calculate best paths from it to every possible destination in the network. The collection of best paths forms the node's routing table.
Link state messages from the nodes are propagated throughout the network so the nodes can determine the connectivity of all other nodes in the network to build a map of the network. A node may detect a change in topology of the network, such as in response to a failed link. The node can send link state messages in the network to inform other nodes of the topology change so the map and best paths can be recomputed at each node.